class Solution {
public:
    vector<int>count;
    vector<int> countSmaller(vector<int>& nums) {
        vector<int>help(nums.size());
        count.resize(nums.size(),0);
        vector<int>indexarr(nums.size(),0);
        for(int i=0;i<nums.size();i++)
        {
            indexarr[i]=i;
        }
        vector<int>indexhelp(nums.size(),0);
        mergesort(nums,help,0,nums.size()-1,indexarr,indexhelp);
        return count;
    }

    void mergesort(vector<int>& nums,vector<int>& help,int left,int right,vector<int>&indexarr,vector<int>&indexhelp)
    {
        //left；0 mid=0 right:1
        //[0,0][1,1]
        if(left>=right) return;
        int mid=left+(right-left)/2;
        mergesort(nums,help,left,mid,indexarr,indexhelp);
        mergesort(nums,help,mid+1,right,indexarr,indexhelp);
        int begin1=left,end1=mid,begin2=mid+1,end2=right,index=left;
        while(begin1<=end1&&begin2<=end2)
        {
            if(nums[begin1]>nums[begin2])
            {
                count[indexarr[begin1]]+=right-begin2+1;
                indexhelp[index]=indexarr[begin1];
                help[index++]=nums[begin1++];
            }
            else
            {
                indexhelp[index]=indexarr[begin2];
                help[index++]=nums[begin2++];
            }
        }
        while(begin1<=end1)
        {
            indexhelp[index]=indexarr[begin1];
            help[index++]=nums[begin1++];
        }
        while(begin2<=end2)
        {
            indexhelp[index]=indexarr[begin2];
            help[index++]=nums[begin2++];
        }
        for(int i=left;i<=right;i++) 
        {
            nums[i]=help[i];
            indexarr[i]=indexhelp[i];
        }
    }
};